package com.huangyi;

import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

public class Main {
    public static void main(String[] args) {
       //数组中的第K个最大元素
        class Solution {
            public int findKthLargest(int[] nums, int k) {
                return qselect(nums, 0, nums.length - 1, k);
            }

            // 三路快选：找第 k 大（k 从 1 开始）
            private static int qselect(int[] nums, int l, int r, int k) {
                if (l == r) return nums[l];

                int left = l - 1, right = r + 1, i = l;
                int key = nums[ThreadLocalRandom.current().nextInt(l, r + 1)];

                // 三路分区：<key | ==key | >key
                while (i < right) {
                    if (nums[i] < key) {
                        swap(nums, ++left, i++);
                    } else if (nums[i] > key) {
                        swap(nums, --right, i); // i 不动
                    } else {
                        i++;
                    }
                }
                // [l, left] < key; [left+1, right-1] == key; [right, r] > key
                int b = right - left - 1;   // 等于段
                int c = r - right + 1;      // 大于段（更大）

                if (k <= c) {
                    return qselect(nums, right, r, k);            // 在 >key 段
                } else if (k <= c + b) {
                    return key;                                    // 落在 ==key 段
                } else {
                    return qselect(nums, l, left, k - (c + b));    // 去 <key 段
                }
            }

            private static void swap(int[] a, int x, int y) {
                int t = a[x]; a[x] = a[y]; a[y] = t;
            }
        }


        //库存管理III
        class Solution2 {
            public int[] inventoryManagement(int[] stock, int cnt) {
                int n = stock.length;
                if (cnt <= 0) return new int[0];
                if (cnt >= n) return Arrays.copyOf(stock, n);

                int l = 0, r = n - 1;
                int k = cnt; // 还需要的数量

                while (l <= r) {
                    int left = l - 1, right = r + 1, i = l;
                    int key = stock[ThreadLocalRandom.current().nextInt(l, r + 1)];

                    while (i < right) {
                        if (stock[i] < key) {
                            swap(stock, ++left, i++);
                        } else if (stock[i] > key) {
                            swap(stock, --right, i); // i 不动
                        } else {
                            i++;
                        }
                    }
                    // [l, left] < key; [left+1, right-1] == key; [right, r] > key
                    int a = left - l + 1;     // <key
                    int b = right - left - 1; // ==key

                    if (a >= k) {
                        r = left;                 // 递左段
                    } else if (a + b >= k) {
                        break;                    // 覆盖住了前缀，停
                    } else {
                        k -= (a + b);             // 进入右段继续收集
                        l = right;
                    }
                }

                int[] ans = Arrays.copyOf(stock, cnt); // 无序即可
                // 若需要升序：Arrays.sort(ans);
                return ans;
            }

            private static void swap(int[] a, int x, int y) {
                int t = a[x]; a[x] = a[y]; a[y] = t;
            }
        }

    }
}